package Test;

/**
 * 给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。
 * 如果两个链表不存在相交节点，返回 null
 * 1.分别求两个链表的长度lenA,lenB. 假定pl长 , ps短. while循环当pl不为空时 , 遍历链表
 * 2.然后将pl,ps指回来 pl = headA ps = headB
 * 3.计算两个链表的差值 , int len = lenA-lenB;如果相减是正值 返回.如果相减是负值,说明lenB长度大于lenA .
 *   然后将pl 给headB,ps给headA len = lenB- lenA(保证了len一定是正数,pl指定的是一定是最长的,ps指定的一定是最短的
 * 4.走差值步. 当len!=0时,将pl向后走,步数减减. 当pl!=ps时,pl向后走,ps向后走.
 *   如果pl==null,返回null.否则返回pl
 */
public class Test05 {
    public MySingleList.ListNode getIntersectionNode(MySingleList.ListNode headA, MySingleList.ListNode headB) {
        if (headA == null && headB == null) {
            return null;
        }
        int lenA = 0;
        int lenB = 0;
        MySingleList.ListNode pl = headA;
        MySingleList.ListNode ps = headB;

        while (pl != null) {
            lenA++;
            pl = pl.next;
        }
        while (ps != null) {
            lenB++;
            ps = ps.next;
        }
        pl = headA;
        ps = headB;
        int len = lenA - lenB;
        if (len < 0) {
            pl = headB;
            ps = headA;
            len = lenB - lenA;
        }
        while (len != 0) {
            pl = pl.next;
            len--;
        }
        while (pl != ps) {
            pl = pl.next;
            ps = ps.next;
        }

        /*if ( pl == null) {
            return null;
        }*/
        return pl;
    }
}


